package 代码随想录_动态规划.子序列问题.回文;

/**
 * @author zx
 * @create 2022-06-22 11:19
 */
public class 最长回文子串_5 {
    /**
     * @return 中心拓展法
     * 背
     * 这道题是一个细节题
     */
    public String longestPalindrome(String s) {
        int left = 0,right = 0;
        //对所有的长度求出最大值,即得到最终答案
        for(int i = 0;i < s.length();i++){
            int len = Math.max(extend(s,i,i),extend(s,i,i + 1));
            if(len > right - left){
                left = i - (len - 1) / 2;
                right = i + len / 2;
            }
        }
        return s.substring(left,right + 1);
    }
    //以当前回文中心尝试扩展,直到无法扩展为止
    //此时的回文串长度即为此[回文中心]下的最长回文串长度.
    private int extend(String s,int i,int j){
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
            i--;
            j++;
        }
        return j - i - 1;
    }

    /**
     * @return 动态规划(题解里找的最适合自己的)
     */
    public String longestPalindrome2(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int start = 0;//最长回文串的起点
        int end = 0;  //最长回文串的终点
        int len = 1;  //最长回文串的长度
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (s.charAt(j) == s.charAt(i) && (i - j <= 2 || dp[j + 1][i - 1])) {
                    dp[j][i] = true;//注意这里特殊
                    if (i - j + 1 > len) {
                        len = i - j + 1;
                        start = j;
                        end = i;

                    }
                }

            }

        }
        return s.substring(start, end + 1);
    }
}
